package video.simple100;


import org.junit.Test;

/***
 * 112. 路径总和
 */
public class LeetCode112 {


    @Test
    public void test() {
        TreeNode root = new TreeNode(5,
                new TreeNode(4,
                        new TreeNode(11,
                                new TreeNode(7),
                                new TreeNode(2)),
                        null),
                new TreeNode(8,
                        new TreeNode(13),
                        new TreeNode(4,
                                null,
                                new TreeNode(1))
                )

        );
        System.out.println(hasPathSum(root, 22));
    }

    public boolean hasPathSum(TreeNode root, int targetSum) {
        // 是否找到某一条线 == targetSum 值的线
        // 0= 没有  1=有
        int[] res = {0};
        nextNode(root, 0, targetSum, res);
        return res[0] == 1;
    }


    /**
     *
     * @author wangsong
     * @param root  当前递归到的节点
     * @param num  递归到节点之前的所有父节点和
     * @param targetSum 目标值
     * @param res  结果值（保存最后判断的结果用的）
     * @date 2022/4/7 0007 22:54
     * @return void
     * @version 1.0.0
     */
    void nextNode(TreeNode root, Integer num, int targetSum, int[] res) {
        if (res[0] == 1 || root == null) {
            return;
        }
        num += root.val;
        // 1、 左递归获取往左边线的值
        nextNode(root.left, num, targetSum, res);
        // 2、 右递归获取往右边线的值
        nextNode(root.right, num, targetSum, res);
        // 3、 判断是否找到等于targetSum目标值的线
        if (root.left == null && root.right == null) {
            if (num == targetSum) {
                // 找到了
                res[0] = 1;
                // System.out.println("找到了,字节点值为：" + root.val);
            }
        }
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}


//给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
//
//        叶子节点 是指没有子节点的节点。
//
//         
//
//        示例 1：
//
//
//        输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
//        输出：true
//        解释：等于目标和的根节点到叶节点路径如上图所示。
//        示例 2：
//
//
//        输入：root = [1,2,3], targetSum = 5
//        输出：false
//        解释：树中存在两条根节点到叶子节点的路径：
//        (1 --> 2): 和为 3
//        (1 --> 3): 和为 4
//        不存在 sum = 5 的根节点到叶子节点的路径。
//        示例 3：
//
//        输入：root = [], targetSum = 0
//        输出：false
//        解释：由于树是空的，所以不存在根节点到叶子节点的路径。
//         
//
//        提示：
//
//        树中节点的数目在范围 [0, 5000] 内
//        -1000 <= Node.val <= 1000
//        -1000 <= targetSum <= 1000
//
//        来源：力扣（LeetCode）
//        链接：https://leetcode-cn.com/problems/path-sum
//        著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。